package com.fyl.basic_algorithm.dynamic_programming;


/**
 * @Description:
 * @author:fyl
 * @date 2021/4/18 19:57
 * @Modified By:
 * @Modified Date:
 */
public class Pack {

    /**
     * 动态规划解决背包问题
     *
     * @param weight 物品重量
     * @param n      物品个数
     * @param w      背包可承受重量
     * @return 最大重量
     */
    public int knapsack(int[] weight, int n, int w) {
        boolean[][] states = new boolean[n][w + 1];  //默认false
        states[0][0] = true; //第一行的数据要特殊处理，可以利用哨兵优化
        if (weight[0] < w) {
            states[0][weight[0]] = true;
        }
        for (int i = 0; i < n; i++) {  //动态规划状态转移
            for (int j = 0; j <= w; j++) {  //不把第i个物品放入背包
                if (states[i - 1][j]) states[i][j] = states[i - 1][j];
            }
            for (int j = 0; j <= w - weight[i]; j++) {  //把第i个物品放入背包
                if (states[i - 1][j]) states[i][j + weight[i]] = true;
            }
        }

        for (int i = w; i >= 0; --i) {
            if (states[n - 1][i]) return i;
        }

        return 0;
    }

    /**
     * 用一维数组解决
     *
     * @param items 物品重量
     * @param n     物品个数
     * @param w     背包可承受重量
     * @return 最大重量
     */
    public static int knapsack2(int[] items, int n, int w) {
        boolean[] states = new boolean[w + 1];  //默认false
        states[0] = true;
        if (items[0] < w) {
            states[items[0]] = true;
        }
        for (int i = 0; i < n; i++) {  //动态规划
            for (int j = w - items[i]; j >= 0; j--) {  //把第i个物品放入背包
                if (states[j] == true) states[j + items[i]] = true;
            }
        }
        for (int i = w; i >= 0; i--) {  //输出结果
            if (states[i]) return i;
        }
        return 0;
    }

    /**
     * 在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大
     *
     * @param weight 物品重量
     * @param value  物品价值
     * @param n      物品个数
     * @param w      背包可承受重量
     * @return 最大总价值
     */
    public static int knapsack3(int[] weight, int[] value, int n, int w) {
        int[][] states = new int[n][w + 1]; //储存当前状态对应的最大总价值
        for (int i = 0; i < n; i++) {  //初始化states，
            for (int j = 0; j < w + 1; j++) {
                states[i][j] = -1;
            }
        }

        states[0][0] = 0;
        if (weight[0] <= w) {
            states[0][weight[0]] = value[0];
        }
        //动态规划，状态转移
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= w; j++) {  //不选择第i个物品
                if (states[i - 1][j] >= 0) states[i][j] = states[i][j];
            }
            for (int j = 0; j <= w - weight[i]; j++) {  //选择第i个物品
                if (states[i - 1][j] >= 0) {
                    int v = states[i - 1][j] + value[i];
                    if (v > states[i][j + weight[i]]) {
                        states[i][j + weight[i]] = v;
                    }
                }
            }
        }
        //找出最大值
        int maxValue = -1;
        for (int i = 0; i <= w; i++) {
            if (states[n - 1][i] > maxValue) maxValue = states[n - 1][i];
        }
        return maxValue;
    }

    /**
     * 双11减满活动用动态规划解决
     *
     * @param items 商品价格
     * @param n     商品个数
     * @param w     减满条件，如200
     */
    public static void double11advance(int[] items, int n, int w) {
        boolean[][] states = new boolean[n][3 * w + 1];  //超过减满的3被无意义
        states[0][0] = true;
        if (items[0] <= 3 * w) {
            states[0][items[0]] = true;
        }
        //动态规划
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 3 * w; j++) {
                if (states[i - 1][j]) states[i][j] = states[i - 1][j];
            }
            for (int j = 0; j < 3 * w - items[i]; j++) {
                if (states[i - 1][j]) states[i][j + items[i]] = true;
            }
        }

        int j;
        for (j = w; j < 3 * w + 1; j++) {
            if (states[n - 1][j]) break;  //输出结果大于等于w的最小值
        }
        if (j == 3 * w + 1) return; //没有可行解
        for (int i = n - 1; i >= 1; i--) {  // i表示二维数组中的行，j表示列
            if (j - items[i] >= 0 && states[i - 1][j - items[i]]) {
                System.out.println(items[i] + " "); //购买这个商品
                j = j - items[i];
            }
        }
        if (j != 0) {
            System.out.println(items[0]);
        }
    }
}
